#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct Treenode {
	char _val;
	Treenode* _left;
	Treenode* _right;
	Treenode(const char& c)
		:_val(c),
		_left(nullptr),
		_right(nullptr) {

	}
};

Treenode* CreateTreeByPreorder(const string& s, int& index) {
	if (s[index] == '#') {
		index++;
		return nullptr;
	}
	Treenode* root = new Treenode(s[index]);
	index++;
	root->_left = CreateTreeByPreorder(s, index);
	root->_right = CreateTreeByPreorder(s, index);
	return root;
}
Treenode* CreateTree(const string& s) {
	Treenode* root;
	int index = 0;
	int end = s.size();
	root=CreateTreeByPreorder(s, index);
	return root;
}
void PreOrder(Treenode* root) {
	if (root == nullptr) {
		return;
	}
	cout << root->_val;
	PreOrder(root->_left);
	PreOrder(root->_right);
}
void InOrder(Treenode* root) {
	if (root == nullptr) {
		return;
	}
	InOrder(root->_left);
	cout << root->_val;
	InOrder(root->_right);
}
void PostOrder(Treenode* root) {
	if (root == nullptr) {
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	cout << root->_val;
}
int LeafNums(Treenode* root) {
	if (root == nullptr) {
		return 0;
	}
	int num = 0;
	if (root->_left == nullptr && root->_right == nullptr) {
		num++;
	}
	return num + LeafNums(root->_left) + LeafNums(root->_right);
}


void test1() {
	string s("FCA##DB###EHM###G##");
	Treenode* root = CreateTree(s);
	PreOrder(root);
	cout << endl;
	InOrder(root);
	cout << endl;
	PostOrder(root);
	cout << endl;
	cout << LeafNums(root) << endl;
}

int main() {
	test1();
	return 0;
}